ACM_Algorithm

红黑树学习感想

红黑树在很多地方有应用，在阅读《STL源码剖析》的时候遇到红黑树，费了一番功夫才看明白。

感想

学习红黑树的过程中，看了一些网络上别人的讲解，但是看来看去仍然不能够理解，也不明白每个操作的缘由。
算法导论这样给出红黑树的定义：

1
2
3
4
5
6
一般的，红黑树，满足一下性质，即只有满足一下性质的树，我们才称之为红黑树：
1）每个结点要么是红的，要么是黑的。
2）根结点是黑的。
3）每个叶结点，即空结点是黑的。
4）如果一个结点是红的，那么它的俩个儿子都是黑的。
5）对每个结点，从该结点到其子孙结点的所有路径上包含相同数目的黑结点。

如果你理解了红黑树之后再来看这些性质，每一条都是非常正确的，但是在初学的时候看这样的定义就一脸懵逼。
另外红黑其实表示的是边的颜色，而不是节点的颜色。
最后找到了红黑树作者的课件,作者的课件内容编排合理、图解透彻细腻并且易懂，带你一点一点地讲清楚由来以及演化过程。

1
2
3
4
//课件地址
链接: https://pan.baidu.com/s/1FeIS0Af8E3tM0ElHN9-mkA 提取码: 4pqd
//csdn上也有该课件，有人这样评价：
//Sedgewick 红黑树PPT ，地球上描述红黑树最透彻的PPT，绝对值得一看！

几点总结如下：

  • 好的教材对自学来说非常重要，内容编排合理以及辅助图解可以极大地减小学习成本。
  • 学习算法一定要从算法的演化过程、思考过程来学，这样才能理解更加深刻。
  • 一定要静下心来学习，过于急躁、急功近利反而更学不进去。

思路

课件写的非常完善，就不再赘述。

应用

  • STL库中的map、set几个关联式容器
  • Java中的Treemap
  • Linux中完全公平调度算法CFS(Completely Fair Schedule)
  • 用红黑树管理进程控制块epoll在内核中的实现，用红黑树管理事件块
  • Nginx中，用红黑树管理timer等

问题

  • 课件page33中的min函数？
  • 课件page57 
    1
    2
    3
    h.left = deleteMax(h.left);
    //为何是h.left,不应该是：
    h.right = deleteMax(h.right);

参考

欢迎与我分享你的看法。
转载请注明出处：http://taowusheng.cn/